package graphStudy;

import java.util.ArrayList;
import java.util.List;

public class FindOrder {

    /**
     * LeetCode T210 课程表
     * @param args
     */
    public static void main(String[] args) {
        int[][] pre = new int[][]{{1, 0}};
        findOrder(2, pre);

    }

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int index = 0;
        int[] indegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++){
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++){
            indegree[prerequisites[i][0]]++;
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        //使用indegree作为栈
        int top = -1;
        for (int i = 0; i < numCourses; i++){
            if (indegree[i] == 0){
                res[index++] = i;
                indegree[i] = top;
                top = i;
            }
        }
        //栈为空时，跳出循环
        while (top != -1){
            //出栈
            int cur = top;
            top = indegree[top];
            List<Integer> edges = graph.get(cur);
            for (Integer edge : edges) {
                if (--indegree[edge] == 0){
                    res[index++] = edge;
                    indegree[edge] = top;
                    top = edge;
                }
            }
        }
        if (index == numCourses) {
            return res;
        }
        return new int[0];
    }
}
